package com.aaron.leetcode.lc23;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * @author liurong
 * @date 2022/1/26 16:09
 * @version:
 */
//labuladong
public class Solution23_3 {
    int listsNum = 4;

    ListNode[] lists;

    {
        lists = new ListNode[listsNum];
        Random random = new Random();
        for (int index = 0; index < listsNum; index++) {
            List<ListNode> nodes = random.ints(random.ints(1, 1, 10).findFirst().getAsInt(), 0, 100).sorted().mapToObj(ListNode::new).collect(Collectors.toList());
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }
            lists[index] = nodes.get(0);
        }


    }

    {
        lists = new ListNode[listsNum];
        List<List<Integer>> list = Arrays.asList(
                Arrays.asList(14, 17, 25, 29),
                Arrays.asList(5, 6, 37, 67, 73),
                Arrays.asList(24, 46, 48, 65, 79, 87),
                Arrays.asList(13, 28, 39));
        for (int i = 0; i < list.size(); i++) {
            ListNode node = new ListNode(list.get(i).get(0));
            lists[i] = node;
            for (int j = 1; j < list.get(i).size(); j++) {
                ListNode nextNode = new ListNode(list.get(i).get(j));
                node.next = nextNode;
                node = nextNode;
            }
        }
        System.out.println();

    }


    ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b) -> (a.val - b.val));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            //lbld有一个p用来记录当前的node，自己没有，自己处理好前面的，保证优先队列poll出来的和之前的都排好了
            p.next = node;
            //写起来比自己的简略，因为每动一次（动优先队列；在一个list里面移动）都poll、add一个node
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution23_3 solution23_3 = new Solution23_3();
        ListNode ans = solution23_3.mergeKLists(solution23_3.lists);
        while (null != ans) {
            System.out.print(ans.val + " ");
            ans = ans.next;
        }
    }
}




